package io.zhengsh.vvip.leetcode.window;

import java.util.ArrayList;
import java.util.List;

public class Q438_Find_All_Anagrams_In_A_String {

    class Solution {
        public List<Integer> findAnagrams(String s, String p) {
            int sLen = s.length(), pLen = p.length();
            if (sLen < pLen) {
                return new ArrayList<>();
            }

            List<Integer> ans = new ArrayList<>();
            int[] count = new int[26];
            for (int i = 0; i < pLen; i++) {
                ++count[s.charAt(i) - 'a'];
                --count[p.charAt(i) - 'a'];
            }

            int differ = 0;
            for (int j = 0; j < 26; j++) {
                if (count[j] != 0) {
                    ++differ;
                }
            }

            if (differ == 0) {
                ans.add(0);
            }

            for (int i = 0; i < sLen - pLen; i++) {
                // 窗口字母中 s[i] 的数量和字符串 p 中的数量从不同变成相同
                if (count[s.charAt(i) - 'a'] == 1) {
                    --differ;
                }
                // 窗口字母 s[i] 的数量和字符串 p 中的数量从相同变得不同
                else if (count[s.charAt(i) - 'a'] == 0) {
                    ++differ;
                }
                --count[s.charAt(i) - 'a'];

                // 窗口中字母 s[i + pLen] 的互谅与字符串 p 中的数量从不同变得相同
                if (count[s.charAt(i + pLen) - 'a'] == -1) {
                    --differ;
                }
                // 窗口中字母 s[i + pLen] 的互谅与字符串 p 中的数量从相同变得不同
                else if (count[s.charAt(i + pLen) - 'a'] == 0) {
                    ++differ;
                }

                ++count[s.charAt(i + pLen) - 'a'];
                if (differ == 0) {
                    ans.add(i + 1);
                }
            }
            return ans;
        }
    }
}
